import LinkedListNode from './LinkedListNode.js';
import Comparator from '../../utils/comparator/Comparator.js';


export default class LinkedList {
  /**
   * 构造函数，初始化链表
   * @param {Function} [comparatorFunction] - 可选的比较函数，用于比较节点值
   */
  constructor(comparatorFunction) {
    /** @var LinkedListNode 头节点 */
    this.head = null;

    /** @var LinkedListNode 尾节点 */
    this.tail = null;

    // 初始化比较器
    this.compare = new Comparator(comparatorFunction);
  }

  /**
   * 在链表头部插入一个新节点
   * @param {*} value - 新节点的值
   * @return {LinkedList} - 返回链表本身，以便链式调用
   */
  prepend(value) {
    // 创建一个新节点，并将其设置为新的头节点
    const newNode = new LinkedListNode(value, this.head);
    this.head = newNode;

    // 如果链表为空，将新节点设置为尾节点
    if (!this.tail) {
      this.tail = newNode;
    }

    return this;
  }

  /**
   * 在链表尾部插入一个新节点
   * @param {*} value - 新节点的值
   * @return {LinkedList} - 返回链表本身，以便链式调用
   */
  append(value) {
    const newNode = new LinkedListNode(value);

    // 如果链表为空，将新节点设置为头节点和尾节点
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return this;
    }

    // 将新节点附加到链表的末尾
    this.tail.next = newNode;
    this.tail = newNode;

    return this;
  }

  /**
   * 在指定位置插入一个新节点
   * @param {*} value - 新节点的值
   * @param {number} index - 插入位置的索引
   * @return {LinkedList} - 返回链表本身，以便链式调用
   */
  insert(value, rawIndex) {
    const index = rawIndex < 0 ? 0 : rawIndex;
    if (index === 0) {
      this.prepend(value);
    } else {
      let count = 1;
      let currentNode = this.head;
      const newNode = new LinkedListNode(value);
      while (currentNode) {
        if (count === index) break;
        currentNode = currentNode.next;
        count += 1;
      }
      if (currentNode) {
        newNode.next = currentNode.next;
        currentNode.next = newNode;
      } else {
        if (this.tail) {
          this.tail.next = newNode;
          this.tail = newNode;
        } else {
          this.head = newNode;
          this.tail = newNode;
        }
      }
    }
    return this;
  }

  /**
   * 删除链表中第一个匹配给定值的节点
   * @param {*} value - 要删除的节点的值
   * @return {LinkedListNode} - 返回被删除的节点，如果未找到则返回null
   */
  delete(value) {
    if (!this.head) {
      return null;
    }

    let deletedNode = null;

    // 如果头节点需要被删除，将下一个节点设置为新的头节点
    while (this.head && this.compare.equal(this.head.value, value)) {
      deletedNode = this.head;
      this.head = this.head.next;
    }

    let currentNode = this.head;
    // 删除匹配值的节点
    while (currentNode.next) {
      if (this.compare.equal(currentNode.next.value, value)) {
        deletedNode = currentNode.next;
        currentNode.next = currentNode.next.next;
      } else {
        currentNode = currentNode.next;
      }
    }

    // 如果尾节点需要被删除，更新尾节点
    if (this.compare.equal(this.tail.value, value)) {
      this.tail = currentNode;
    }

    return deletedNode;
  }

  /**
   * 根据给定的值或回调函数查找节点
   * @param {Object} findParams - 包含值或回调函数的参数对象
   * @param {*} findParams.value - 要查找的值
   * @param {function} [findParams.callback] - 查找的回调函数
   * @return {LinkedListNode} - 找到的节点，如果未找到则返回null
   */
  find({ value = undefined, callback = undefined }) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;
    // 遍历链表，查找匹配的节点
    while (currentNode) {
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }
      if (value !== undefined && this.compare.equal(currentNode.value, value)) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }

    return null;
  }

  /**
   * 删除并返回链表的尾节点
   * @return {LinkedListNode} - 被删除的尾节点
   */
  deleteTail() {
    const deletedTail = this.tail;

    if (this.head === this.tail) {
      // 如果链表只有一个节点，将头尾节点置为null
      this.head = null;
      this.tail = null;
      return deletedTail;
    }

    // 找到倒数第二个节点，将其next置为null
    let currentNode = this.head;
    while (currentNode.next) {
      if (!currentNode.next.next) {
        currentNode.next = null;
      } else {
        currentNode = currentNode.next;
      }
    }

    this.tail = currentNode;
    return deletedTail;
  }

  /**
   * 删除并返回链表的头节点
   * @return {LinkedListNode} - 被删除的头节点
   */
  deleteHead() {
    if (!this.head) {
      return null;
    }

    const deletedHead = this.head;

    // 如果链表只有一个节点，将头尾节点置为null
    if (!this.head.next) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
    }

    return deletedHead;
  }

  /**
   * 将数组转换为链表
   * @param {*[]} values - 要转换为链表的数组
   * @return {LinkedList} - 返回链表本身，以便链式调用
   */
  fromArray(values) {
    values.forEach((value) => this.append(value));
    return this;
  }

  /**
   * 将链表转换为数组
   * @return {LinkedListNode[]} - 转换后的数组
   */
  toArray() {
    const nodes = [];
    let currentNode = this.head;
    while (currentNode) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }
    return nodes;
  }

  /**
   * 将链表转换为字符串表示
   * @param {function} [callback] - 可选的回调函数，用于处理每个节点的值
   * @return {string} - 转换后的字符串
   */
  toString(callback) {
    return this.toArray().map((node) => node.toString(callback)).join(',');
  }

  /**
   * 反转链表
   * @returns {LinkedList} - 反转后的链表
   */
  reverse() {
    let currNode = this.head;
    let prevNode = null;
    let nextNode = null;

    // 遍历链表，反转节点的指向
    while (currNode) {
      nextNode = currNode.next;
      currNode.next = prevNode;
      prevNode = currNode;
      currNode = nextNode;
    }

    // 重新设置头尾节点
    this.tail = this.head;
    this.head = prevNode;

    return this;
  }
}


